/// @tags: MoDui Bitset
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

int const N = 1e5 + 5, M = 2e4 + 5e3 + 1, B = 417;

int n, m;
int a[N], hash[N], ans[M], cnt[N];
bitset<N> bs[M], tmp;

struct Query {
  int l, r, id, bel;
  inline bool operator<(Query const &rhs) const {
    return bel == rhs.bel ? ((bel & 1) ? r < rhs.r : r > rhs.r) : bel < rhs.bel;
  }
} q[M * 3];

inline void add(int p) {
  tmp[a[p] + cnt[a[p]]] = true;
  cnt[a[p]]++;
}

inline void del(int p) {
  cnt[a[p]]--;
  tmp[a[p] + cnt[a[p]]] = false;
}

inline void solve(int t) {
  int L = 1, R = 0;
  memset(ans, 0, sizeof(ans));
  memset(cnt, 0, sizeof(cnt));
  tmp.reset();
  int tot = 0;
  for (int i = 1; i <= t; ++i) {
    bs[i].reset();
    ++tot;
    cin >> q[tot].l >> q[tot].r;
    q[tot].id = i;
    q[tot].bel = (q[tot].l - 1) / B + 1;
    ans[i] += q[tot].r - q[tot].l + 1;
    ++tot;
    cin >> q[tot].l >> q[tot].r;
    q[tot].id = i;
    q[tot].bel = (q[tot].l - 1) / B + 1;
    ans[i] += q[tot].r - q[tot].l + 1;
    ++tot;
    cin >> q[tot].l >> q[tot].r;
    q[tot].id = i;
    q[tot].bel = (q[tot].l - 1) / B + 1;
    ans[i] += q[tot].r - q[tot].l + 1;
  }
  sort(q + 1, q + tot + 1);
  for (int i = 1; i <= tot; ++i) {
    while (R < q[i].r) add(++R);
    while (L > q[i].l) add(--L);
    while (R > q[i].r) del(R--);
    while (L < q[i].l) del(L++);
    if (!bs[q[i].id].none()) bs[q[i].id] &= tmp;
    else
      bs[q[i].id] = tmp;
  }
  for (int i = 1; i <= t; ++i) cout << ans[i] - 3 * bs[i].count() << '\n';
}

inline int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i], hash[i] = a[i];
  sort(hash + 1, hash + n + 1);
  for (int i = 1; i <= n; ++i) a[i] = lower_bound(hash + 1, hash + n + 1, a[i]) - hash;
  while (m > 0) {
    if (m >= M) solve(M - 1), m -= M - 1;
    else
      solve(m), m = 0;
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4688 [Ynoi2016] 掉进兔子洞.in", "r", stdin);
  freopen("P4688 [Ynoi2016] 掉进兔子洞.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
